#include <stdlib.h>
#include <stdio.h>

#define SIZE 10
#define MIN -65535;

void exchange(int *a, int *b){
	*a = *a + *b;
	*b = *a - *b;
	*a = *a - *b;
}

void max_heapify(int A[], int i, int len){
	int max_index = len - 1;
	int l;
	int r;
	int largest = i;
	
	if(i > max_index)
		return;
	while(largest <= max_index){
		l = (largest << 1) + 1;
		r = (largest << 1) + 2;
		if(l <= max_index)
			if(A[l] > A[largest]) largest = l;
		if(r <= max_index)
			if(A[r] > A[largest]) largest = r;
		if(largest == i) break;
		else exchange(&A[largest], &A[i]);
	}
}

int heap_maximum(int A[]){
	return A[0];
}

int heap_extract_max(int A[], int *len){
	if(*len < 1)
		exit(0);
	int max_index = *len - 1;
	int max = A[0];

	A[0] = A[max_index];
	*len = *len - 1;
	max_heapify(A, 0, *len);
	return max;
}

void heap_increase_key(int A[], int i, int key, int len){
	int parent;
	if(i > (len - 1))
                return;
	if(key < A[i])
		return;
	A[i] = key;
	while(i > 0){
		parent = (i-1)/2;
		if(A[parent] < A[i]){
			exchange(&A[parent], &A[i]);
			i = parent;
		}else break;
	}
}

int *max_heap_insert(int A[], int key, int *len){
	int i;
	int last = *len;
	*len += 1;
	int *B = (int *)malloc(sizeof(int) * (last+1));	//增加数组长度不能简单的A[last+1] = MIN,而应该手动分配新内存(堆)，静态的数组在栈中
	for(i=0;i<last;i++)
		B[i] = A[i];
	B[last] = MIN;
	heap_increase_key(B, last, key, *len);
	return B;
}

void max_heap_delete(int A[], int i, int *len){
	int last = *len - 1;
	int min, l, r;
	if(i > last || i < 0)
		return;
	
	exchange(&A[i], &A[last]);
	*len -= 1;
	last -= 1;
	while(i < last){
		min = i;
		l = (i << 1) + 1;
		r = (i << 1) + 2; 
		if(l <= last && A[l] > A[min]) min = l;
		if(r <= last && A[r] > A[min]) min = r;
		if(i != min){
			exchange(&A[i], &A[min]);
			i = min;
		}else break;
	}
}

void print_array(int A[], int len){
	int i;
	for(i=0;i<len;i++)
		printf("%d, ",A[i]);
	printf("\n");
}

int main(void){
	int A[SIZE] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
	int len = sizeof(A)/sizeof(int);
	print_array(A, len);
	heap_increase_key(A, 8, 15, len);
	print_array(A, len);
	int *B = max_heap_insert(A, 10, &len);
	print_array(B, len);
	max_heap_delete(B, 1, &len);
	print_array(B, len);
}
